package listbyorder.access001_100.test37;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/31 9:12
 */
public class Solution2 {

    public void solveSudoku(char[][] board) {
        dfs(board, 0, 0);
    }

    private boolean dfs(char[][] board, int r, int c) {
        if (r == 9) {
            return true;
        }
        if (c == 9) {
            return dfs(board, r + 1, 0);
        }
        if (board[r][c] != '.') {
            return dfs(board, r, c + 1);
        }
        for (int i = 1; i <= 9; i++) {
            boolean ok = true;

            char cur = (char) (i + ('1' - 1));

            for (int j = 0; j < 9; j++) {
                if (board[r][j] == cur) {
                    ok = false;
                }
            }

            for (int j = 0; j < 9; j++) {
                if (board[j][c] == cur) {
                    ok = false;
                }
            }

            int c_r = (r / 3) * 3;
            int c_c = (c / 3) * 3;
            for (int j = c_r; j < c_r + 3; j++) {
                for (int k = c_c; k < c_c + 3; k++) {
                    if (board[j][k] == cur) {
                        ok = false;
                    }
                }
            }

            if (ok) {
                board[r][c] = cur;
                if (dfs(board, r, c + 1)) {
                    return true;
                }
                board[r][c] = '.';
            }
        }
        return false;
    }
}
